/*
 * File:   mst_kruckal.c
 * Author: aishwarya
 *
 * Created on March 12, 2011, 11:08 AM
 * Kruskal's (Greedy) algorithm to find Minimum Spanning Tree.
 */

#include "graph_algos.h"
#include "../DataStructures/avdtech.h"
#include "../DataStructures/disjoint_sets.h"

int mst_wtcompare(const void *a, const void *b) {
    EDGE_PAIR *x = (EDGE_PAIR *) a;
    EDGE_PAIR *y = (EDGE_PAIR *) b;

    if (x->w > y->w) return 1;
    if (x->w < y->w) return -1;

    return 0;
}

weight mst_kruskal(GRAPH *g) {
    int i, total = 0 ;
    Parent x, y;
    weight cost=0;
    EDGE_PAIR *epair ;
    int *path ;
    disjoint_sets s ;
    int edge_pairs ;

    set_init(&s, g->nvertices) ;
    
    /* Sort the edges into non-decreasing order by weight w */
    epair = (EDGE_PAIR *) malloc(g->nedges * sizeof(EDGE_PAIR)) ;
    path = (int *) malloc(g->nedges * sizeof(int)) ;
    edge_pairs = graph_create_edge_pairs(g, epair) ;

    qsort(epair, edge_pairs, sizeof (EDGE_PAIR), mst_wtcompare);
    
    for (i = 0; i < edge_pairs; i++) {
        x = set_find(&s, epair[i].u);
        y = set_find(&s, epair[i].v);        
        if (x != y) {
            cost += epair[i].w;
            set_union_p(&s, x, y);
            path[total++] = i;
            if (total == g->nvertices - 1)
                break;
        }
    }
    
/*
    for (i = 0; i < total; i++)
        LOG(LOG_INFO, "Edge (%d,%d)=%d", epair[path[i]].u, epair[path[i]].v, epair[path[i]].w);
*/

    set_clean(&s) ;
    free(epair) ;
    free(path) ;

    return cost;
}